#ifndef GAMEENGINE_GEOMETRY_TOPOLOGY_HALFEDGE_H
#define GAMEENGINE_GEOMETRY_TOPOLOGY_HALFEDGE_H

#include <GameEngine/Geometry/geometry_settings.h>

#include <list>


#ifdef GAMEENGINE_NAMESPACES
namespace GameEngine {
#endif

template <class T> class HalfEdge;
template <class T> class HalfEdgeFace;

//=================================================================================

//! Class used to represent half-edge vertices
/*!
 *  A half-edge vertex combines information about the position of the vertex and about
 *  the half-edge that points to this vertex. It is templated by the type of vertex to
 *  maximize reusability of the class.
 *
 @sa The HalfEdge class to represent half-edges.
 */
template <class T>
class HalfEdgeVertex {

public:
	HalfEdgeVertex();
	HalfEdgeVertex(HalfEdge<T>* edge, const T& pos);
	HalfEdgeVertex(const HalfEdgeVertex& rhs);
	virtual ~HalfEdgeVertex();
	HalfEdgeVertex& operator=(const HalfEdgeVertex& rhs);

	HalfEdge<T>* leaving_edge() const;
	bool set_leaving_edge(HalfEdge<T>* edge);
	const T& location() const;
	bool set_location(const T& location);

	std::list< HalfEdge<T>* > edges_around_vertex() const;
	std::list< HalfEdgeFace<T>* > faces_around_vertex() const;

protected:
	//! Edge associated to this vertex
	HalfEdge<T>* leaving_edge_;

	//! Location
	T location_;
};

//=================================================================================

//! Class used to represent half-edge faces
/*!
 *  A half-edge face stores information about one of the half-edges of the face (it does not
 *  matter which one).
 *
 @sa The HalfEdge class to represent half-edges.
 */
template <class T>
class HalfEdgeFace {

public:
	//! Enumerator indicating the type of the face
	enum FaceType {
		//! Valid half-edge faces
		ValidFace,
		//! Half-edge face does not define a closed loop
		/*!
		 *  An example of such a face could be: (example is written in pseudo-code)
		 *  @code
		 *  edge1->next = edge2
		 *  edge2->next = edge3
		 *  edge3->next = nil
		 *  @endcode
		 *  Hence, the face defines a path between edge1 and edge3 but never loops back
		 *  to edge1.
		 */
		OpenPathFace,
		//! Half-edge face defines a closed, but invalid loop
		/*!
		 *  An example of such a face could be: (example is written in pseudo-code)
		 *  @code
		 *  edge1->next = edge2
		 *  edge2->next = edge3
		 *  edge3->next = edge4
		 *  edge4->next = edge2
		 *  @endcode
		 *  Hence, the face defines a loop between edge2, edge3 and edge4, but
		 *  never loops back to edge1.
		 */
		InvalidLoopFace
	};

	//! Enumerator indicating the type of the face
	enum AdjacencyType {
		//! Valid half-edge adjacency
		/*!
		 *  A face adjacency is valid if all of its boundaries are defined (boundaries can
		 *  either be connected to real faces or to the virtual border), can be traversed
		 *  and are oriented consistently
		 */
		ValidAdjacency,
		//! Ill-defined half-edge adjacency
		/*!
		 *  A face adjacency is ill-defined if at least one of its boundaries are not defined
		 *  (i.e., that one of its half-edges had a null pointer for the opposite half-edge)
		 */
		OpenAdjacency,
		//! Adjacency is incorrect due to inconsistent orientations of the faces
		/*!
		 *  A face has inconsistent orientation if at least one of the adjacent faces is not
		 *  turning in the same sense, which means that two opposite half-edges are leaving
		 *  the same vertex
		 */
		InconsistentOrientationAdjacency,
		//! Adjacency could not be defined
		/*!
		 *  This issue typically happens when the internal state of the face itself is ill-defined
		 *  (i.e., that its FaceType is not equal to ValidFace), which often means that the half-edges
		 *  of the face cannot be traversed to test the consistency of their adjacency informations.
		 */
		 UndefinedAdjacency
	};

public:
	HalfEdgeFace();
	HalfEdgeFace(HalfEdge<T>* edge);
	HalfEdgeFace(const HalfEdgeFace& rhs);
	virtual ~HalfEdgeFace();
	HalfEdgeFace& operator=(const HalfEdgeFace& rhs);

	HalfEdge<T>* edge() const;
	bool set_edge(HalfEdge<T>* edge);

	HalfEdge<T>* find_common_edge(const HalfEdgeFace& rhs) const;
	HalfEdgeVertex<T>* find_common_vertex(const HalfEdgeFace& rhs) const;

	FaceType face_type() const;
	AdjacencyType adjacency_type() const;

protected:
	//! Edge associated to this face
	HalfEdge<T>* edge_;
};

//=================================================================================

//! Class used to represent half-edges
/*!
 *  The half-edge data structure is an advanced type of boundary representation for polygons that maintains
 *  adjacency information between the polygons, while allowing constant-time access to the neighbours, the
 *  shared edges, the vertices, etc.
 *
 *  Strictly speaking, the half-edge data structure solely works for manifold surfaces. Borders (either external
 *  or internal) are however permitted by this implementation, due to the definition of a virtual "exterior"
 *  face. All edges that belong to the exterior face have a null face pointer; the exterior face can therefore
 *  not be iterated. Please note that it is possible to avoid this limitation by the definition of an actual
 *  exterior face rather than a virtual one; this design should be adopted at a higher level (typically on the
 *  half-edge mesh itself).
 *
 *  In general, the half-edge data structure is well suited when the mesh should be dynamically updated by
 *  client code, depending on some external events (a typical example is adaptative mesh refinement, where
 *  mesh is solely refined where it is needed). Another possible use is when frequent adjacency queries are
 *  required, e.g., in surface flooding algorithms. For static meshes, however, more compact and efficient
 *  data structures are likely to exist, making half-edges a bad candidate.
 *
 *  For more informations on half-edges, please see Max McGuire's description, which provides an excellent
 *  introduction to how half-edges work and examples on how to iterate through this structure:
 *                   http://www.flipcode.com/archives/The_Half-Edge_Data_Structure.shtml
 *
 *  Another good resource is Ryan Holmes' description, which details more advanced issues related to the
 *  half-edge data structure, including the pros and the cons of using it (the design of a virtual exterior
 *  face is directly inspired from his description):
 *                   http://www.holmes3d.net/graphics/dcel/
 *
 @sa The HalfEdgeVertex class for half-edge vertices, the HalfEdgeFace class for half-edge faces, and the
     HalfEdgeMesh class to manipulate meshes made of half-edges.
 */
template <class T>
class HalfEdge {

public:
	//! Typedef used to handle HalfEdge faces
	typedef HalfEdgeFace<T> Face;
	//! Typedef used to handle HalfEdge vertices
	typedef HalfEdgeVertex<T> Vertex;

	//! Enumerator indicating the type of the edge
	enum Type {
		//! Invalid half-edges
		/*!
		 *  A half-edge can be invalid for two reasons: (i) it has no opposite edge, or (ii) it
		 *  has no associated vertex.
		 */
		Invalid,
		//! Half-edges that belong to the virtual border face
		VirtualBorder,
		//! Half-edges that are shared by two real faces
		Internal
	};

public:
	HalfEdge();
	HalfEdge(Vertex* origin, Face* face, HalfEdge* next_edge, HalfEdge* opposite_edge = nil);
	HalfEdge(const HalfEdge& rhs);
	virtual ~HalfEdge();
	HalfEdge& operator=(const HalfEdge& rhs);

	bool exterior_edge() const;

	Vertex* origin() const;
	Face* face() const;
	HalfEdge* next_edge() const;
	HalfEdge* opposite_edge() const;

	HalfEdge* get_previous_edge() const;

	bool set_origin(Vertex* origin);
	bool set_face(Face* face);
	bool set_next_edge(HalfEdge* next_edge);
	bool set_opposite_edge(HalfEdge* opposite_edge, bool notify_other_edge = true);

	Type edge_type() const;

	std::list< HalfEdgeFace<T>* > faces_around_edge() const;

protected:
	//! Vertex from which this half-edge is leaving
	Vertex* origin_;

	//! Face of this half-edge
	/*!
	 @note This is currently useless since the face solely stores information about an half-edge, and
	       any half-edge of the face is valid. If no more information needs to be stored by the face,
		   the HalfEdgeFace class will disappear for being no more useful. Another idea would be to
		   create two half-edge classes: the first one would have no clue about its face, making the
		   structure more compact, whereas the second one would know informations about its face for
		   whatever purposes client code may need.
	 */
	Face* face_;

	//! Next edge of the polygon
	HalfEdge* next_edge_;

	//! Opposite edge
	HalfEdge* opposite_edge_;
};

#ifdef GAMEENGINE_NAMESPACES
} // namespace GameEngine
#endif

#include <GameEngine/Geometry/Topology/halfedge.hpp>

#endif
